package main.java.indi.zyj.classic150;

import main.java.indi.zyj.hot100.base.ListNode;

public class ReverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode top = new ListNode(-1);
        top.next = head;
        ListNode start = top, end = top;

        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            // 因为你不知道是不是遍历够了k个才退出循环的
            if (end == null) {
                break;
            }
            ListNode nextStart = end.next;
            end.next = null;
            ListNode reverseStart = start.next;
            start.next = reverseNode(reverseStart);
            reverseStart.next = nextStart;
            start = reverseStart;
            end = reverseStart;
        }

        return top.next;
    }


    public ListNode reverseNode(ListNode head) {
        ListNode top = new ListNode(-1);
        ListNode p = head, q;
        while (p != null) {
            q = p.next;
            p.next = top.next;
            top.next = p;
            p = q;
        }
        return top.next;
    }

}
